This paper addresses the problem of improving the query performance of the triangular expansion algorithm (TEA) for computing visibility regions by finding the most advantageous instance of the triangular mesh, the preprocessing structure. The TEA recursively traverses the mesh while keeping track of the visible region, the set of all points visible from a query point in a polygonal world. We show that the measured query time is approximately proportional to the number of triangle edge expansions during the mesh traversal. We propose a new type of triangular mesh that minimizes the expected number of expansions assuming the query points are drawn from a known probability distribution. We design a heuristic method to approximate the mesh and evaluate the approach on many challenging instances that resemble real-world environments. The proposed mesh improves the mean query times by 12-16% compared to the reference constrained Delaunay triangulation. The approach is suitable to boost offline applications that require computing millions of queries without addressing the preprocessing time. The implementation is publicly available to replicate our experiments and serve the community.

This paper addresses the sensor-placement problem (SPP) within the context of discretizing large, complex continuous 2D environments into graphs for efficient task-oriented route planning. The SPP aims to minimize the number of sensors required to achieve a user-defined coverage ratio while considering a general visibility model. We propose the hybrid filtering heuristic (HFH) framework, which enhances or combines outputs of existing sensor-placement methods, incorporating a filtering step. This step eliminates redundant sensors or those contributing marginally to the coverage, ensuring the coverage ratio remains within the desired interval. We implement two versions of HFH: the basic version and a variant, HFHB, incorporating a preprocessing technique known as bucketing to accelerate region clipping. We evaluate HFH and HFHB on a dataset of large, complex polygonal environments, comparing them to several baseline methods under both unlimited and limited-range omnidirectional visibility models. The results demonstrate that HFH and HFHB outperform baselines in terms of the number of sensors required to achieve the desired coverage ratio. Additionally, HFHB significantly reduces the runtime of more competitive baseline methods. We also adapt HFHB to a visibility model with localization uncertainty, demonstrating its effectiveness up to a certain level of uncertainty.

Given a mapped environment, we formulate the problem of visually tracking and following an evader using a probabilistic framework. In this work, we consider a non-holonomic robot with a limited visibility depth sensor in an indoor environment with obstacles. The mobile robot that follows the target is considered a pursuer and the agent being followed is considered an evader. We propose a probabilistic framework for both the pursuer and evader to achieve their conflicting goals. We introduce a smart evader that has information about the location of the pursuer. The goal of this variant of the evader is to avoid being tracked by the pursuer by using the visibility region information obtained from the pursuer, to further challenge the proposed smart pursuer. To validate the efficiency of the framework, we conduct several experiments in simulation by using Gazebo and evaluate the success rate of tracking an evader in various environments with different pursuer to evader speed ratios. Through our experiments we validate our hypothesis that a smart pursuer tracks an evader more effectively than a pursuer that just navigates in the environment randomly. We also validate that an evader that is aware of the actions of the pursuer is more successful at avoiding getting tracked by a smart pursuer than a random evader. Finally, we empirically show that while a smart pursuer does increase it's average success rate of tracking compared to a random pursuer, there is an increased variance in its success rate distribution when the evader becomes aware of its actions.

We study the problem of incorporating risk while making combinatorial decisions under uncertainty. We formulate a discrete submodular maximization problem for selecting a set using Conditional-Value-at-Risk (CVaR), a risk metric commonly used in financial analysis. While CVaR has recently been used in optimization of linear costs functions in robotics, we take the first stages towards extending this to discrete submodular optimization and provide several positive results. Specifically, we propose the Sequential Greedy Algorithm that provides an approximation guarantee on finding the maxima of the CVaR cost function under a matroidal constraint. The approximation guarantee shows that the solution produced by our algorithm is within a constant factor of the optimal and an additive term that depends on the optimal. Our analysis uses the curvature of the submodular set function, and proves that the algorithm runs in polynomial time. This formulates a number of combinatorial optimization problems that appear in robotics. We use two such problems, vehicle assignment under uncertainty for mobility-on-demand and sensor selection with failures for environmental monitoring, as case studies to demonstrate the efficacy of our formulation.

Given a polygon P of n vertices, the method to define a visibility polygon from a single point, q, is a well established Most digital games are goal-oriented; players are given an problem (Ghosh 2007), of time complexity Θ(n log(n)). We initial position and have to reach a certain goal position or use the well known angular plane-sweep algorithm (Asano state within a virtual level. Many generative methods to create 1985) to construct a visibility region V (q), giving us a starshaped such levels have been defined, and are able to create engaging polygonal region defined by the existing edge set, levels (Dormans and Bakkes 2011), while making filtered according to visibility from q. Figure 2 shows such a sure the game's fundamental puzzle structure in terms of region in light purple for point q.